package demo2;

public class MySingleLinked {
    //链表的回文结构
    public boolean chkPalindrome(ListNode A) {

    }
    //链表分割
    //方法二
    public ListNode partition(ListNode pHead, int x){
        ListNode as = null;
        ListNode ae = null;
        ListNode bs = null;
        ListNode be = null;
        ListNode cur = pHead;
        while(cur != null){
            ListNode curN = cur.next;
            if(cur.val < x){
                if(as == null){
                    as = cur;
                    ae = as;
                }else {
                    ae.next = cur;
                    ae = ae.next;
                }
            }else {
                if(bs == null){
                    bs = cur;
                    be = bs;
                }else {
                    be.next = cur;
                    be = be.next;
                }
            }
            cur = cur.next;
        }
        if(be.next != null){
            be.next = null;
        }
        if(as == null){
            return bs;
        }
        if(bs == null){
            return as;
        }
        ae.next = bs;
        return as;
    }
    //方法一
    public ListNode partition1(ListNode pHead, int x) {
        ListNode node1 = new ListNode(-1);
        ListNode node2 = new ListNode(-1);
        ListNode cur1 = node1;
        ListNode cur2 = node2;
        while(pHead != null){
            if(pHead.val < x){
            cur1.next = pHead;
            cur1 = cur1.next;
            }else {
                cur2.next = pHead;
                cur2 = cur2.next;
            }
            pHead  = pHead.next;
        }
        cur2.next = null;
        cur1.next = node2.next;
        return node1.next;
    }

    //合并两个有序链表
    public ListNode mergeTwoListsn (ListNode list1,ListNode list2){
        MySingleLinked code = new MySingleLinked();
        code.addLast(1);
        ListNode head = code.head;
        ListNode cur = head;
        if(list1 == null && list2 == null){
            return list1;
        }
        while(list1 != null && list2 != null){
            if(list1.val <= list2.val){
                cur.next = list1;
                list1 = list1.next;
            }else {
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        if(list1 == null){
            cur.next = list2;
        }else {
            cur.next = list1;
        }
        head = code.head.next;
        return head;
    }
    //找出单向链表中倒数第 k 个节点
    //方法二
    public int kthToLast2(ListNode head, int k) {
    ListNode cur = head;
    ListNode curN = head;
    if(head == null){
        return 0;
    }
    int num = k-1;
    for(int i = 0; i < num ;i++){
        curN = curN.next;
        if(curN == null){
            return 0;
        }
    }
    while(curN.next != null){
        cur = cur.next;
        curN = curN.next;
    }
    return cur.val;
    }
    //方法一
    public int kthToLast1(ListNode head, int k) {
        if(head == null){
            return -1;
        }
        int num1 = size(head);
        if(k < 0 || k > num1){
            return -1;
        }
     int num = num1 - k;
     for(int i = 0 ; i < num ;i++){
         head = head.next;
     }
     return head.val;
    }
    //链表的中间结点
    public ListNode middleNode(ListNode head) {

     ListNode cur = head;
     ListNode prev = head;
     while(prev != null && prev.next != null){
         cur = cur.next;
         prev = prev.next.next;
     }

     return cur;
    }
    static class ListNode {
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode head;

    public void addLast(int data) {

        ListNode node = new ListNode(data);

        ListNode cur = this.head;
        if (this.head == null) {
            this.head = node;
            return;
        }
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = node;
    }

    //反转链表
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode cur = head.next;
        ListNode curN = head.next.next;
        head.next = null;
        while (curN != null) {
            cur.next = head;
            head = cur;
            cur = curN;
            curN = curN.next;
        }

        cur.next = head;
        head = cur;
        return head;
    }

    public void show() {
        ListNode cur = this.head;
        if (head == null) {
            return;
        }
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    public void show(ListNode head){
        ListNode cur = head;
        if (head == null) {
            return;
        }
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }
    public int size(){
        ListNode cur = this.head;
        if(cur == null ){
            return 0;
        }

        int count = 0;
        while(cur != null){
            count++;
            cur = cur.next;
        }
        return count;
    }
    public int size(ListNode head){
        ListNode cur = head;
        if(cur == null ){
            return 0;
        }

        int count = 0;
        while(cur != null){
            count++;
            cur = cur.next;
        }
        return count;
    }
}

